<html>
<head><meta charset="utf-8"><title>Q: union find data structures · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html">Q: union find data structures</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="154574220"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154574220" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154574220">(Jan 07 2019 at 14:57)</a>:</h4>
<p>I have a question about chalk/polonius implomatation.</p>
<p>For Cargo's resolver, I have been looking into persistent union find data structures. The papers I am reading have had 2 examples of where these are useful:  for type resolution and for Prolog implementations. So my question is does chalk/polonius already have an implementation if not would a crate be useful for chalk/polonius?</p>



<a name="154575505"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154575505" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154575505">(Jan 07 2019 at 15:12)</a>:</h4>
<p>(deleted)</p>



<a name="154577670"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154577670" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154577670">(Jan 07 2019 at 15:41)</a>:</h4>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> in fact, ena supports a persistent union-find, though I've not played with it much to measure performance or anything</p>



<a name="154577693"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154577693" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154577693">(Jan 07 2019 at 15:41)</a>:</h4>
<p>er, sorry, to answer your question, we are using <a href="https://crates.io/crates/ena" target="_blank" title="https://crates.io/crates/ena">https://crates.io/crates/ena</a></p>



<a name="154577702"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154577702" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154577702">(Jan 07 2019 at 15:41)</a>:</h4>
<p>(polonius doens't need that)</p>



<a name="154577891"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154577891" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154577891">(Jan 07 2019 at 15:43)</a>:</h4>
<p>Where can I find the persistent  veriton, is it on master?</p>



<a name="154578743"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578743" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578743">(Jan 07 2019 at 15:55)</a>:</h4>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> in some sense, it's <em>always</em> persistent -- you just <code>clone</code> the table whenever you want</p>



<a name="154578754"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578754" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578754">(Jan 07 2019 at 15:55)</a>:</h4>
<p>that said, the <code>persistent</code> feature enables one that uses a persistent vector under the hood</p>



<a name="154578761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578761">(Jan 07 2019 at 15:55)</a>:</h4>
<p>this makes cloning O(1) instead of O(n)</p>



<a name="154578764"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578764" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578764">(Jan 07 2019 at 15:55)</a>:</h4>
<p>note that this does not mean it is faster</p>



<a name="154578767"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578767" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578767">(Jan 07 2019 at 15:55)</a>:</h4>
<p>I've usually found the opposite</p>



<a name="154578768"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578768" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578768">(Jan 07 2019 at 15:55)</a>:</h4>
<p><a href="https://github.com/nikomatsakis/ena/blob/49d9270d95910e303061128938dafce0ae79a45e/Cargo.toml#L15" target="_blank" title="https://github.com/nikomatsakis/ena/blob/49d9270d95910e303061128938dafce0ae79a45e/Cargo.toml#L15">https://github.com/nikomatsakis/ena/blob/49d9270d95910e303061128938dafce0ae79a45e/Cargo.toml#L15</a></p>



<a name="154578838"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578838" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578838">(Jan 07 2019 at 15:56)</a>:</h4>
<p>if you enable that  feature, you can create a <code>UnificationTable&lt;Persistent&gt;</code> I think</p>



<a name="154578841"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578841" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578841">(Jan 07 2019 at 15:56)</a>:</h4>
<p>where the <code>Persistent</code> type is <a href="https://github.com/nikomatsakis/ena/blob/master/src/unify/mod.rs#L41" target="_blank" title="https://github.com/nikomatsakis/ena/blob/master/src/unify/mod.rs#L41">defined here</a></p>



<a name="154578866"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578866" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578866">(Jan 07 2019 at 15:57)</a>:</h4>
<p>here are some tests: <a href="https://github.com/nikomatsakis/ena/blob/master/src/unify/tests.rs#L50" target="_blank" title="https://github.com/nikomatsakis/ena/blob/master/src/unify/tests.rs#L50">link</a></p>



<a name="154578891"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578891" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578891">(Jan 07 2019 at 15:57)</a>:</h4>
<p>it might be interesting to make a version based on <a href="http://im.rs" target="_blank" title="http://im.rs">im.rs</a> or something, should be possible</p>



<a name="154578976"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154578976" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154578976">(Jan 07 2019 at 15:58)</a>:</h4>
<p>there is a <a href="https://github.com/nikomatsakis/ena/blob/master/src/unify/backing_vec.rs#L16-L17" target="_blank" title="https://github.com/nikomatsakis/ena/blob/master/src/unify/backing_vec.rs#L16-L17">trait</a> that controls the backing store, here is the <a href="https://github.com/nikomatsakis/ena/blob/master/src/unify/backing_vec.rs#L147" target="_blank" title="https://github.com/nikomatsakis/ena/blob/master/src/unify/backing_vec.rs#L147">implementation for persistent vectors</a></p>



<a name="154579005"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579005" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579005">(Jan 07 2019 at 15:58)</a>:</h4>
<p>(as an aside, I've been thinking it would make sense to revamp ena for some time but anyway.... the basics are right)</p>



<a name="154579181"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579181" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579181">(Jan 07 2019 at 16:01)</a>:</h4>
<p>Thanks for all the links!</p>



<a name="154579195"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579195" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579195">(Jan 07 2019 at 16:01)</a>:</h4>
<p>Let me see if I can say it back.</p>



<a name="154579305"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579305" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579305">(Jan 07 2019 at 16:03)</a>:</h4>
<p>rustc and chalk use a ena. A persistent version is available there, but is largely not used as it is slower.</p>



<a name="154579340"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579340" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579340">(Jan 07 2019 at 16:03)</a>:</h4>
<p>Work to make it faster would be interesting to its manteners.</p>



<a name="154579419"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579419" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579419">(Jan 07 2019 at 16:04)</a>:</h4>
<p>sounds roughly right. Chalk in particular might benefit from a persistent setup, as it does some cloning</p>



<a name="154579422"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579422" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579422">(Jan 07 2019 at 16:04)</a>:</h4>
<p>tbh I've just not benmarked it much</p>



<a name="154579450"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579450" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579450">(Jan 07 2019 at 16:05)</a>:</h4>
<p>there are also alternative strategies for impl'ing union find, though I think they're not <em>much</em> different</p>



<a name="154579459"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579459" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579459">(Jan 07 2019 at 16:05)</a>:</h4>
<p>e.g. minikanren's impl is intended to be persistent</p>



<a name="154579586"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579586" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579586">(Jan 07 2019 at 16:07)</a>:</h4>
<p>The papers I am reading say that "just swapping out the backing sore for a persistent version, is to slow in practice", I can find the exact quote if you'd like.</p>



<a name="154579610"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579610" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579610">(Jan 07 2019 at 16:07)</a>:</h4>
<p>seems plausible</p>



<a name="154579767"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154579767" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154579767">(Jan 07 2019 at 16:09)</a>:</h4>
<p>They have a page describing exactly why that destroys the Big O of the normal version.</p>



<a name="154580012"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154580012" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154580012">(Jan 07 2019 at 16:12)</a>:</h4>
<p>Thanks for the info! I will continue researching, and try to report back to ena!</p>



<a name="154584848"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154584848" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154584848">(Jan 07 2019 at 17:22)</a>:</h4>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> FWIW I know petgraph has a UnionFind data structure as well but I don't think it's persistent -- might be worth looking at though.</p>



<a name="154584981"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154584981" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154584981">(Jan 07 2019 at 17:24)</a>:</h4>
<p>Do you have a link for minikanren's impl?</p>



<a name="154590515"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154590515" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154590515">(Jan 07 2019 at 18:45)</a>:</h4>
<p>not really</p>



<a name="154600995"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154600995" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154600995">(Jan 07 2019 at 21:02)</a>:</h4>
<p>Ba humbug. I miss read the abstract. The paper was about the "ask the same object for what is value used to be" type of persistent not the "fast clone" " type of persistent. (they are related, but not the same) It is not faster for the case we care about.</p>



<a name="154606940"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154606940" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> blitzerr <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154606940">(Jan 07 2019 at 22:30)</a>:</h4>
<blockquote>
<p>The papers I am reading say that "just swapping out the backing sore for a persistent version, is to slow in practice", I can find the exact quote if you'd like.</p>
</blockquote>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> , can you paste a link to the papers you are hinting towards ?</p>



<a name="154608580"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154608580" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154608580">(Jan 07 2019 at 22:58)</a>:</h4>
<p>The one that turned out to be about the wrong problem is<br>
<a href="https://link.springer.com/chapter/10.1007/BFb0028283" target="_blank" title="https://link.springer.com/chapter/10.1007/BFb0028283">https://link.springer.com/chapter/10.1007/BFb0028283</a></p>



<a name="154608710"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154608710" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154608710">(Jan 07 2019 at 23:01)</a>:</h4>
<p>The quote I had in mind is from <br>
<a href="https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf" target="_blank" title="https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf">https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf</a></p>
<p>But it goes on to suggest a somost automatic version of the snapshot idea that is already in ena</p>



<a name="154615635"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Q%3A%20union%20find%20data%20structures/near/154615635" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> blitzerr <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Q.3A.20union.20find.20data.20structures.html#154615635">(Jan 08 2019 at 01:29)</a>:</h4>
<p>thanks a lot <span class="user-mention" data-user-id="120179">@Eh2406</span></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>